package leetcode_600;

import java.util.Arrays;

/**
 *@author 周杨
 *StudentAttendanceRecordII_552 给定n表示有n条记录 给出有多少种学生考勤合格的可能
 *describe:用动态规划 
 *2018年9月13日 下午1:12:23
 */
public class StudentAttendanceRecordII_552 {
	public static void main(String[] args) {
		System.out.println(Integer.MAX_VALUE);
		StudentAttendanceRecordII_552 test=new StudentAttendanceRecordII_552();
		System.out.println(test.checkRecord(28));
		System.out.println(test.checkRecord(29));
		System.out.println(test.checkRecord(30));
		System.out.println(test.checkRecord(31));
	}
	int [][][] dp;
    int MOD = 1000000007;
    
    public int checkRecord(int n) {
        dp = new int[n + 1][3][2];
        for(int [][] arr : dp)
            for(int [] bar : arr)
                Arrays.fill(bar, -1);
        
        return helper(n, 0, 0) % MOD;
    }
    
    public int helper(int n, int L, int A){
        if(n == 0) return 1;
        
        if(dp[n][L][A] != -1)
            return dp[n][L][A] % MOD;
        
        int sol = 0;
        sol += helper(n - 1, 0, A) % MOD; //P
        sol %= MOD;
        
        if(L <= 1)
            sol += helper(n - 1, L + 1, A) % MOD; //L Sequence
        
        sol %= MOD;
        if(A == 0)
            sol += helper(n - 1, 0, 1) % MOD; //A
        
        sol %= MOD;
        dp[n][L][A] = sol;
        return sol;
    }
	/**
	 * describe:正确解 用动态规划 只是怎样解 数组都要越界 还可以越界
	 * 2018年9月13日 下午1:11:37
	 */
	public int checkRecord1(int n) {
		if(n==1)
			return 3;
        long dp[]=new long[6];
        //记录6个dp 其中dp[0][1][2]表示无A 连续的L个数
        dp[0]=1;
        dp[1]=1;
        dp[3]=1;
        for(int i=2;i<=n;++i) {
        	long sum1=dp[0]+dp[1]+dp[2];
        	long sum2=dp[3]+dp[4]+dp[5];
        	//加入A 那么只能选没有A的前三者 更新到后三者里去
        	long dp3=sum1;
        	//加入L 
        	long dp1=dp[0];
        	long dp2=dp[1];
        	long dp4=dp[3];
        	long dp5=dp[4];
        	//加入P
        	long dp0=sum1;
            dp3+=sum2;
            dp[0]=dp0;
            dp[1]=dp1;
            dp[2]=dp2;
            dp[3]=dp3;
            dp[4]=dp4;
            dp[5]=dp5;
        }
        return (int) ((dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5])%(1000000007));
    }
}
